package folder.main.exp0.linksMapping;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map.Entry;

import folder.model.network.Network;
import folder.model.node.Node;
import folder.model.virtual.VirtualLink;
import folder.model.virtual.VirtualNetwork;
import folder.model.virtual.VirtualNode;

public class ShortestPath extends LinksMappingAlgorithm
{
	public ShortestPath( String name )
	{
		super( name );
	}
	
	protected double[][][] linkMapping( VirtualNetwork virtualNetwork, Network network, LinkedHashMap< VirtualNode, Node > nodeMapping, double availableBWs[][] )
	{
		List< VirtualLink > virtualLinks = virtualNetwork.getVirtualLinks();
		int nodeNumber = network.getNumberNodes();
		
		double linkMapping[][][] = new double[ virtualLinks.size() ][ nodeNumber ][ nodeNumber ];
		boolean isLinkMapping = true;
		
		double availableBandwidths[][] = new double[ nodeNumber ][ nodeNumber ];
		double costs[][] = new double[ nodeNumber ][ nodeNumber ];
		
		for( int i = 0; i < nodeNumber; i++ )
			for( int j = 0; j < nodeNumber; j++ )
			{
				availableBandwidths[ i ][ j ] = availableBWs[ i ][ j ];
				costs[ i ][ j ] = availableBWs[ i ][ j ];
			}
		
		for( int i = 0; i < nodeNumber; i++ )
			for( int j = 0; j < nodeNumber; j++ )
				if( costs[ i ][ j ] != 0 )
					costs[ i ][ j ] = 1 / costs[ i ][ j ];
		
		for( VirtualLink virtualLink: virtualLinks )
		{
			int iNodeA = 0;
			int iNodeB = 0;
			
			Iterator< Entry< VirtualNode, Node > > iterator = nodeMapping.entrySet().iterator();
		    
		    while( iterator.hasNext() )
		    {
		    	boolean isiNodeA = false;
		    	boolean isiNodeB = false;
		    	
		    	Entry< VirtualNode, Node > pair = iterator.next();
		    	int iVirtualNode = pair.getKey().getIdentifier();
		    	
		    	if( virtualLink.getVirtualNodeA().getIdentifier() == iVirtualNode )
		    	{
		    		isiNodeA = true;
		    		iNodeA = pair.getValue().getIdentifier();
		    	}
		    	
		    	if( virtualLink.getVirtualNodeB().getIdentifier() == iVirtualNode )
		    	{
		    		isiNodeB = true;
		    		iNodeB = pair.getValue().getIdentifier();
		    	}
		    	
		    	if( isiNodeA && isiNodeB )
		    		break;
		    }
		    
		    double cost = 1 / virtualLink.getBandwidth();
		    
			int iPreviousNodes[] = null;
			
			if( this.getCostMetric().equals( DISTANCE_COST ) )
				iPreviousNodes = this.iShortestDistanceNodes( network, iNodeA, availableBandwidths, virtualLink.getBandwidth() );
			
			else if( this.getCostMetric().equals( BW_COST ) )
				iPreviousNodes = this.iHigherAvailableBandwidthNodes( network, iNodeA, costs, cost );
			
			List< Integer > shortPath = new ArrayList< Integer >();
			
			if( iPreviousNodes == null )
			{
				isLinkMapping = false;
				
				break;
			}
			else
				shortPath = this.shortPath( iPreviousNodes, iNodeA, iNodeB );
			
			if( shortPath.get( shortPath.size() - 1 ) != iNodeB )
			{
				isLinkMapping = false;
				
				break;
			}

			for( int i = 0; i < shortPath.size() - 1; i++ )
			{
				int iNode = shortPath.get( i );
				int iNextNode = shortPath.get( i + 1 );
				
				linkMapping[ virtualLink.getIdentifier() ][ iNode ][ iNextNode ] = virtualLink.getBandwidth();
				
				costs[ iNode ][ iNextNode ] = 1 / costs[ iNode ][ iNextNode ] - 1 / Math.abs( cost );
				costs[ iNode ][ iNextNode ] = 1 / costs[ iNode ][ iNextNode ];
				costs[ iNextNode ][ iNode ] = costs[ iNode ][ iNextNode ];
				
			    availableBandwidths[ iNode ][ iNextNode ] -= virtualLink.getBandwidth();
				availableBandwidths[ iNextNode ][ iNode ] -= virtualLink.getBandwidth();
			}
		}
		
		if( isLinkMapping == false )
			linkMapping = null;
		
		return linkMapping;
	}
	
	private List< Integer > shortPath( int iPreviousNodes[], int iNodeA, int iNodeB )
	{
		List< Integer > shortPath = new ArrayList< Integer >();
		int iPreviousNodeB = iNodeB;
		
		while( iPreviousNodeB != iNodeA && iPreviousNodeB > -1 )
		{
			shortPath.add( 0, iPreviousNodeB );
			iPreviousNodeB = iPreviousNodes[ iPreviousNodeB ];
		}
		
		shortPath.add( 0, iNodeA );
		
		return shortPath;
	}
	
	private int[] iHigherAvailableBandwidthNodes( Network network, int iNodeA, double availableBandwidths[][], double cost )
	{	
		int nodeNumber = network.getNumberNodes();
		double shortestDistances[] = new double[ nodeNumber ];
			 
		for( int i = 0; i < shortestDistances.length; i++ )
			shortestDistances[ i ] = Integer.MAX_VALUE;
		 
		shortestDistances[ iNodeA ] = 0;
		
		boolean isVisited[] = new boolean[ nodeNumber ];
		int iShortestDistanceNodes[] = new int[ nodeNumber ];
		
		for( int i = 0; i < shortestDistances.length; i++ )
		{
			int iShortestDistanceNode = this.iShortestDistanceNode( shortestDistances, isVisited );
		
			if( iShortestDistanceNode == -1 )
				break;
			
			isVisited[ iShortestDistanceNode ] = true;
		 
			List< Integer > iNeighbourNodes = new ArrayList< Integer >();
			 
			for( int j = 0; j < nodeNumber; j++ )
				if( availableBandwidths[ iShortestDistanceNode ][ j ] != 0 )
					if( availableBandwidths[ iShortestDistanceNode ][ j ] < Math.abs( cost ) )
						iNeighbourNodes.add( j );
			 
			for( int j = 0; j < iNeighbourNodes.size(); j++ )
			{
				int iNeighbourNode = iNeighbourNodes.get( j );
				double shortestDistance = shortestDistances[ iShortestDistanceNode ] + availableBandwidths[ iShortestDistanceNode ][ iNeighbourNode ];
				 
				if( shortestDistance < shortestDistances[ iNeighbourNode ] )
				{
					shortestDistances[ iNeighbourNode ] = shortestDistance;
					iShortestDistanceNodes[ iNeighbourNode ] = iShortestDistanceNode;
				}
			}
		}
	
		return iShortestDistanceNodes;
	}
	
	private int[] iShortestDistanceNodes( Network network, int iNodeA, double availableBandwidths[][], double bandwidth )
	{	
		int nodeNumber = network.getNumberNodes();
		double distances[][] = this.delays( network );
		double shortestDistances[] = new double[ nodeNumber ];
			 
		for( int i = 0; i < shortestDistances.length; i++ )
			shortestDistances[ i ] = Integer.MAX_VALUE;
		
		shortestDistances[ iNodeA ] = 0;
		
		boolean isVisited[] = new boolean[ nodeNumber ];
		
		int iShortestDistanceNodes[] = new int[ nodeNumber ];
		
		for( int i = 0; i < nodeNumber; i++ )
			iShortestDistanceNodes[ i ] = -1;
		
		for( int i = 0; i < shortestDistances.length; i++ )
		{
			int shortestDistanceNodeNumber = this.iShortestDistanceNode( shortestDistances, isVisited );
		
			if( shortestDistanceNodeNumber == -1 )
				break;
			
			isVisited[ shortestDistanceNodeNumber ] = true;
		 
			List< Integer > iNeighbourNodes = new ArrayList< Integer >();
			 
			for( int j = 0; j < nodeNumber; j++ )
				if( availableBandwidths[ shortestDistanceNodeNumber ][ j ] != 0 )
					if( bandwidth < availableBandwidths[ shortestDistanceNodeNumber ][ j ] )
						iNeighbourNodes.add( j );
			 
			for( int j = 0; j < iNeighbourNodes.size(); j++ )
			{
				int iNeighbourNode = iNeighbourNodes.get( j );
				double shortestDistance = shortestDistances[ shortestDistanceNodeNumber ] + distances[ shortestDistanceNodeNumber ][ iNeighbourNode ];
				 
				if( shortestDistance < shortestDistances[ iNeighbourNode ] )
				{
					shortestDistances[ iNeighbourNode ] = shortestDistance;
					iShortestDistanceNodes[ iNeighbourNode ] = shortestDistanceNodeNumber;
				}
			}
		}
		
		for( int i = 0; i < nodeNumber; i++ )
			if( iShortestDistanceNodes[ i ] != -1 )
				return iShortestDistanceNodes;
		
		return null;
	}
	
	private int iShortestDistanceNode( double shortestDistances[], boolean isVisited[] )
	{
		double shortestDistance = Integer.MAX_VALUE;
		int iNode = -1;
		
		for( int i = 0; i < shortestDistances.length; i++ )
			if( !isVisited[ i ] && shortestDistances[ i ] < shortestDistance )
			{
				shortestDistance = shortestDistances[ i ];
				iNode = i;
			}
		
		return iNode;
	}
	
}
